package com.learn.algorithm.dynamic.programming;

public class LeetCode79 {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (f(board, i, j, 0, word.toCharArray())) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean f(char[][] board, int i, int j, int k, char[] word) {
        if (k == word.length) {
            return true;
        }
        if ((i < 0 || i >= board.length || j < 0 || j >= board[0].length) || board[i][j] != word[k]) {
            return false;
        }
        char tmp = board[i][j];
        board[i][j] = 0;
        boolean ans = f(board, i - 1, j, k + 1, word)
                || f(board, i + 1, j, k + 1, word)
                || f(board, i, j - 1, k + 1, word)
                || f(board, i, j + 1, k + 1, word);
        board[i][j] = tmp;
        return ans;
    }
}
